| r11 ➤ r12 |
| 237 | ==독특한 알고리즘== |
| 238 | 이러한 알고리즘들은 배열의 구성 원소들이 안정하게 보존되지 않으며, 오직 '정렬'만을 위한 알고리즘이다. 배열 원소를 삭제해 강제로 정렬을 맞추는 방법 등이 있다. |
| 259 | 스탈린 정렬과 같이 시간복잡도가 [math(O(n))]인 GOAT 알고리즘으로, 배열 요소의 절반을 제거하여 남은 요소가 정렬될 때까지 반복해 정렬된 배열을 얻는다. |
| 260 | ====타노스 정렬 의사코드==== |
| 261 | 누군가가 적어주겠지 배열이 정렬되어 있지 않으면 배열의 딱 절반을 제거(삭제)한다. 이 과정을 배열이 정렬된 상태가 될 때까지 재귀적으로 반복하여 최종적으로 남은 정렬된 부분 배열을 얻는 알고리즘이다. 최악의 경우 원소가 1개만 남을 때까지 제거하므로 반드시 정렬된 결과를 얻게 된다.정렬 의사 코드다음은 타노스 정렬의 로직을 재귀적으로 서술한 코드이다 |
| 262 | ====타노스 정렬 의사코드==== |
| 263 | {{{#!syntax java |
| 264 | JavathanosSort(A[], n): |
| 265 | if (isSorted(A, n)) |
| 266 | return A |
| 267 | else |
| 268 | half_n ← n / 2 |
| 269 | return thanosSort(A[0…half_n-1], half_n) |
| 270 | |
| 271 | isSorted(A[], n): |
| 272 | for i ← 0 to n-2 |
| 273 | if (A[i] > A[i+1]) |
| 274 | return FALSE |
| 275 | return TRUE |
| 276 | }}} |
| 277 | ====분석==== |
| 278 | 타노스 정렬은 배열을 검사하는 데 [math(\Theta(n))]의 시간이 걸리며, 정렬되지 않았을 경우 크기를 절반으로 줄여가며 재귀 호출을 한다. |
| 279 | |
| 280 | '''시간 복잡도''': 각 단계에서 배열을 훑는 시간 [math(n + n/2 + n/4 + \dots + 1)]의 합계이므로 전체 시간 복잡도는 [math(\Theta(n))]이다. |
| 281 | [math(\sum_{i=0}^{\log_2 n} \frac{n}{2^i} = n(1 + \frac{1}{2} + \frac{1}{4} + \dots) < 2n = \Theta(n))] |
| 282 | |
| 283 | '''특징''': 일반적인 정렬과 달리 데이터의 상당수(최대 [math(n-1)]개)를 소멸시킨다는 점에서 매우 파괴적인 알고리즘이다. |
